//543 Diameter of Binary Tree
/*
求一个二叉树的最长直径。直径的定义是二叉树上任意两节点之间的无向距离

Input:
	   1
	  / \
	 2   3
	/ \
   4   5
Output: 3  最长直径是 [4,2,1,3] 和 [5,2,1,3]

*/

// 主函数
int diameterOfBinaryTree(TreeNode *root)
{
	int diameter = 0;
	helper(root, diameter);
	return diameter;
}
// 辅函数
int helper(TreeNode *node, int &diameter) //
{
	if (!node)
	{
		return 0;
	}
	int l = helper(node->left, diameter), r = helper(node->right, diameter);
	diameter = max(l + r, diameter); //
	return max(l, r) + 1;			 //
}



//
class Solution
{
	int ans;
	int depth(TreeNode *rt)
	{
		if (rt == NULL)
		{
			return 0; // 访问到空节点了，返回0
		}
		int L = depth(rt->left);   // 左儿子为根的子树的深度
		int R = depth(rt->right);  // 右儿子为根的子树的深度
		ans = max(ans, L + R + 1); // 计算d_node即L+R+1 并更新ans
		return max(L, R) + 1;	   // 返回该节点为根的子树的深度
	}
 
public:
	int diameterOfBinaryTree(TreeNode *root)
	{
		ans = 1;
		depth(root);
		return ans - 1;
	}
};
